package tandemrepeats;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import tree.Node;
import tree.Tree;

public class SimpleAlgorithms {
		
	public static void findTandems(Tree t){
		t.makeLookupTable();
		Map<Integer, Node> map =t.getMap();
		System.out.println(t.getInputString());

		for(Node v : t.getAllInternalNodes()){
			if(!v.isMarked() && !v.isLeaf()){
				v.setMarked();
				List<Node> leaves = v.getLeafList(new ArrayList<Node>());
				for(Node i: leaves){
					//for each leaf in LL test whether the leaf j = i + depth(v)
					//is in LL.
					
					int j = i.getStartIndex() + v.getDepth();
					Node jNode = map.get(j);
					
					if(leaves.contains(jNode)){
						//If so test whether S[i] != S[i + 2*depth(v)]
						if(	t.getInputString().charAt(i.getStartIndex()-2) != 
							t.getInputString().charAt(i.getStartIndex()+2*v.getDepth()-2)) 
						{
							//there is a branching tandem repeat of length 2D(v) starting at
							//position i iff. both test are true.
							System.out.println("branching tandem repeat at "+i.getStartIndex()
									+ " length " + 2*v.getDepth());
						}
					}
				}
			}
		}
	}

}
